package com.itheima.datastructure.stack;

import java.util.LinkedList;

public class E03InfixToSuffix {

    static int priority(char c){
        return switch (c){
            case '*','/'-> 2;
            case '+','-'-> 1;
            case '('-> 0;
            default -> throw new IllegalArgumentException();
        };
    }

    public static String infixToSuffix(String exp){
        LinkedList<Character> stack = new LinkedList<>();
        StringBuilder sb = new StringBuilder(exp.length());

        for (int i = 0; i < exp.length(); i++) {
            // 取出中缀表达式的所有字符
            char c = exp.charAt(i);
            switch (c){
                case '*','/','+','-' ->{
                    // 表达式根据优先级判断
                    if(stack.isEmpty()){
                        // 栈为空时 无需判断, 直接加入
                        stack.push(c);
                    }else {
                        // 栈不为空 开始判断
                        if(priority(c) > priority(stack.peek())){
                            // 外部符号优先级高于栈内符号 加入栈
                            stack.push(c);
                        }else {
                            // 此时外部符号优先级低于栈内符号 取出栈内元素 放入字符串
                            while(!stack.isEmpty() && priority(stack.peek()) >= priority(c)){
                                sb.append(stack.pop());
                            }
                            // 再加入外部符号
                            stack.push(c);
                        }
                    }
                }
                case '('->{
                    stack.push(c);
                }
                case ')'->{
                    while(!stack.isEmpty() && stack.peek() != '('){
                        sb.append(stack.pop());
                    }
                    // 弹出 (
                    stack.pop();
                }
                default -> {
                    // 数字加入字符串
                    sb.append(c);
                }
            }
        }
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String test = "a+b*c";
        System.out.println(infixToSuffix(test));
    }
}
